from subprocess import Popen, PIPE
from Crypto.Util.number import *
import string
import itertools

def lsb_oracle(cipher):
    cmd = "./lsb_oracle.vmp.exe /decrypt"
    p = Popen(cmd.split(' '), stdout=PIPE, stdin=PIPE, stderr=PIPE)
    out, err = p.communicate("%d\n-1" % cipher)
    return out.split("\n")[1].strip()


ct = 2201077887205099886799419505257984908140690335465327695978150425602737431754769971309809434546937184700758848191008699273369652758836177602723960420562062515168299835193154932988833308912059796574355781073624762083196012981428684386588839182461902362533633141657081892129830969230482783192049720588548332813
n = 120357855677795403326899325832599223460081551820351966764960386843755808156627131345464795713923271678835256422889567749230248389850643801263972231981347496433824450373318688699355320061986161918732508402417281836789242987168090513784426195519707785324458125521673657185406738054328228404365636320530340758959
e = 65537

UB = n
LB = 0
tmp = ct
while True:
    tmp = (tmp * pow(2, e, n)) % n
    if lsb_oracle(tmp) == "0":
        UB = (UB + LB) / 2
    else:
        LB = (UB + LB) / 2
    print "diff", UB - LB
    if UB == LB:
        break

print UB
#UB = 7297754398688551479992982893926808313441848145300010974473258200849533033132314065877866624718303417332957074317200317836574363711380765106879754611578550823918874815772269592230973564148552127539509036145386560409210625029977067141498285782822310296465522986361581199996720134776451190837975669418254590

for x, y in itertools.product(string.printable, repeat=2):
    pt = long_to_bytes(UB)[:-2] + x + y
    print pt
    if ct == pow(bytes_to_long(pt), e, n):
        print "found"
        break

#SharifCTF{65d7551577a6a613c99c2b4023039b0a}
#found




